package com.lhcai.nk;

/**
 * @author lhcstart
 * @create 2023-02-22 17:45
 */


import java.util.HashMap;
import java.util.Scanner;

/**
 * 描述
 * 给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
 * （注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
 * 数据范围：2≤len(numbers)≤10^5，−10≤numbersi≤10^9，0≤target≤10^9
 * 要求：空间复杂度 O(n)，时间复杂度O(nlogn)
 */
public class NC61 {
    /**
     * @param numbers int整型一维数组
     * @param target  int整型
     * @return int整型一维数组
     */
    public int[] twoSum(int[] numbers, int target) {
        // write code here

        //创建map，key为数组的值，value为数组的值的下标
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < numbers.length; i++) {

            if (map.containsKey(target - numbers[i])) {
                //存在则通过target - numbers[i]，获取相应的值（即下标）
                return new int[]{map.get(target - numbers[i]) + 1, i + 1};
            } else {
                map.put(numbers[i], i);
            }
        }
        throw new IllegalArgumentException("No solution");
    }
}
